The invention relates to a method for broadcasting a message in an incomplete partial network of a radio communication network.
Methods for broadcasting messages are used, for example, in the field of mobile, wireless communication, particularly in ad hoc networks. In these networks, the subscribers converge spontaneously and briefly. The arrangement of the mobile subscribers of the network is arbitrary, and can change with respect to space and time. An ad hoc network is normally a mobile, incomplete radio communication network with a decentralized control.
A radio network is only considered complete if a direct radio connection exists between each subscriber pair. Each subscriber is equipped with a radio device, so he can communicate with other subscribers within range. There is no central entity that controls or checks the radio network structured in this manner. Furthermore, the subscribers have local clocks that are equipped with a synchronized time resolution.
Ad hoc networks occur, for example, when mobile computers (laptops, palmtops, etc.) converge at a conference. A plurality of robots communicating with one another and moving in terrain that is difficult to access, such as in deep space, under water or on a battlefield, etc., can also constitute an ad hoc network.
Moreover, there are already miniature devices that are equipped with communication capabilities and are worn on a person. An example is a device named xe2x80x9cLovegetyxe2x80x9d by the Erfolg Co. of Japan, which is described in, among other things, the xe2x80x9cPersonalsxe2x80x9d section of the Tagesspiegel [Daily Mirror] of Jun. 3, 1998, and is intended to help people find a suitable partner. In the future, such devices will be able to form ad hoc networks for performing more complex tasks.
Finally, this application encompasses radio-based, direct vehicle-to-vehicle communication.
In the methods known from the state of the technology for broadcasting messages, the identified communication partners must know the addresses to which the messages are to be sent. If this prerequisite is not met, the known methods cannot be employed, because the necessary information is exceedingly difficult to obtain. Moreover, a direct radio connection between each subscriber pair is often required.
To employ the methods known from the state of the technology, the entire network topology must be known, or be ascertainable by central entities.
The topology of a network usually refers to the distribution of the subscribers or network nodes, and their connection with one another.
It is the object of the invention to provide a method for broadcasting a message in an incomplete radio communication network with a fluctuating number of participants for forwarding the message, in which the message is transmitted as quickly as possible and the subscribers do not necessarily have radio contact with one another at all times.
The object is accomplished by a method for broadcasting a message in an incomplete radio communication network having a fluctuating number of subscribers for forwarding the message, in which each subscriber has a transmitting and receiving device for messages and a positioning system for determining his global position. In accordance with the invention, after receiving the message, subscribers determine their own position and the distance d from the sender of the message, who is likewise a subscriber, and forward the message, with their position, to further subscribers after a predetermined waiting period t, which decreases monotonically as the distance 2 increases.
The method assures an optimum broadcasting of messages, particularly of short messages, data packets and status reports, in a radio communication network when the subscribers have no information about the network topology. The message is transmitted rapidly, from a subscriber acting as the sender of the message to be transmitted, to at least one further subscriber of the partial network; not all subscribers must be within range of the sender of the message.
Unlike approaches known from the state of the technology, the method takes into account the limited knowledge of individual subscribers in the mobile, decentralized radio communication network. The subscribers need not be aware of the complete topology of the network. The method optimizes the message broadcasting with the presupposition of little knowledge about network subscribers and the actual network.
The presupposition that it is not necessary for each subscriber to be familiar with the network topology is practical and reasonable, because the topology can change continuously due to the considerable mobility of some of the subscribers.
A typical example from traffic technology serves to explain this: A two-vehicle accident has occurred on a road. The message about the accident is transmitted to the surroundings by at least one of the involved motor vehicles, as the initiator. The target region for the message includes, for example, a target space having a semicircular outline and a radius of about 10 kilometers. All motor vehicles located within this target space make up the target group for the message about the accident. The position and number of the receivers normally change over time. Therefore, precise knowledge of the network topology inside the target space at a certain time does not assure a necessary quantity of information.
The message transmitted by the first subscriber preferably includes a geometrical description of the target region for his message.
The determination of the boundary of the target region can clarify in advance to which group of receivers the message should be transmitted so that it is put to good use.
In particular, the subscribers can use a decision function to determine their association with the target region, and only forward the message if they are associated with it. In addition to the geometrical boundary of the target region, other decision criteria can be relevant for the decision of whether or not the subscribers are associated with the provided target region.
In a further embodiment of the invention, the subscribers only forward the received message to further subscribers after the first reception of the message. After receiving the message, each subscriber determines whether he is receiving the message for the first time. For this purpose, the subscriber checks a list that includes a message key relating to a unique association of previously-received messages with the respective sender. If the subscriber has already received the message, he engages in no further activities, because he has already forwarded the message to further subscribers. This avoids unnecessary occupation of the radio communication network.
The waiting period t between reception and transmission preferably decreases exponentially as the distance d between the communicating subscribers increases. This structuring of the predetermined waiting period t has proven particularly advantageous in trials.
The dependent claims disclose further advantageous embodiments.